#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<stack>
using namespace std;
//重建二叉树
struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode* m_Right;
	BinaryTreeNode* m_Left;
};

BinaryTreeNode* Consgtruct(int* preorder, int* inorder, int len)
{
	if (preorder == NULL || inorder == NULL || len <= 0)
		return NULL;
	return ConsgtructCore(preorder, preorder + len - 1, inorder, inorder + len - 1);
}
BinaryTreeNode* ConsgtructCore(int* startP, int* endP, int* startI, int* endI)
{
	//前序便利序列的第一个数字是根节点的值
	int rootv = startP[0];
	BinaryTreeNode* root = new BinaryTreeNode();
	root->m_nValue = rootv;
	root->m_Left = root->m_Right = NULL;

	if (startP == endP)
	{
		if (startI == endI&& *startP == *endP)
			return root;
		else
			throw std::exception("Invalid input.");
	}

	//在中序便利中找到根节点的值
	int* rootI = startI;
	while (rootI <= endI && *rootI != rootv)
		++rootI;

	if (rootI == endI && *rootI != rootv)
		throw std::exception("Invalid input.");
	int leftL = rootI - startI;
	int* leftp = startP + leftL;
	if (leftL > 0)
	{
		//构建左子树
		root->m_Left = ConsgtructCore(startP + 1, leftp, startI, rootI - 1);
	}
	if (leftL < endP - startP)
	{
		//构建右子树
		root->m_Right = ConsgtructCore(leftp + 1, endP, rootI + 1, endI);
	}
	return root;
}


